In traditional cryptography it was typically assumed that an attacker only gains access to the input and output values of a secure system. For example, the attacker would be able to observe a plain text going into a system and observe an encrypted text going out of the system. Although an attacker could try to gain an advantage by analyzing such input/output pairs, possibly even using computationally intense methods, he was not thought to have direct access to the system that implemented the input/output behavior.
Recently, it has become necessary to take threat models into account in which it is assumed that an attacker has some knowledge of the implementations. For example, one may consider the threat of side-channel analysis and of reverse engineering. Furthermore, the concerns that previously were mostly associated with security problems have extended to other fields, such as privacy. Although cryptographic systems processing security information such as cryptographic keys remain a prime concern, protection of other programs, e.g., those processing privacy relevant information has also become important.
It has long been known that computer systems leak some information through so-called side-channels. Observing the input-output behavior of a computer system may not provide any useful information on sensitive information, such as secret keys used by the computer system. But a computer system has other channels that may be observed, e.g., its power consumption or electromagnetic radiation; these channels are referred to as side-channels. For example, small variations in the power consumed by different instructions and variations in power consumed while executing instructions may be measured. The measured variation may be correlated to sensitive information, such as cryptographic keys. This additional information on secret information, beyond the observable and intended input-output behavior is termed a side-channel. Through a side-channel a computer system may ‘leak’ secret information during its use. Observing and analyzing a side-channel may give an attacker access to better information than may be obtained from cryptanalysis of input-output behavior only. One known type of side-channel attack is the so-called differential power analysis (DPA).
Current approaches to the side-channel problem introduce randomness in the computation. For example, in between genuine operations that execute the program dummy instructions may be inserted to blur the relationship between power consumption and the data the program is working on.
An even stronger attack on a computer is so called reverse engineering. In many security scenarios attackers may have full access to the computer. This gives them the opportunity to disassemble the program and obtain any information about the computer and program. Given enough effort any key hidden say in a program may be found by an attacker.
Protecting against this attack scenario has proven very difficult. One type of counter measure is so-called white-box cryptography. In white-box cryptography, the key and algorithm are combined. The resulting algorithm only works for one particular key. Next the algorithm may be implemented as a so-called, lookup table network. Computations are transformed into a series of lookups in key-dependent tables. See for example, “White-Box Cryptography and an AES Implementation”, by S. Chow, P. Eisen, H. Johnson, P. C. van Oorschot, for an example of this approach.